package codingforgreat.class50;

import java.util.ArrayList;

class TreeAncestor {
        ArrayList<ArrayList<Integer>> par;
    public TreeAncestor(int n, int[] parent) {
        par = new ArrayList<>();
        int m = 32 - Integer.numberOfLeadingZeros(n);
        for(int i = 0;i < n;i++){
            par.add(i,new ArrayList<>());
            int p = parent[i];
            par.get(i).add(p);
        }
        for(int i = 1;i < m ;i++ ){
        for(int j = 0;j < par.size();j++){
            if(i <= par.get(j).size()){
                int cur =  par.get(j).get(i-1);
                if(cur != -1){
                    if(i  <= par.get(cur).size()){
                        int next =  par.get(cur).get(i-1);
                        par.get(j).add(next);
                    }else{
                        par.get(j).add(-1); // 没有祖先
                    }
                }
            }

        }
        }
    }
    
    public int getKthAncestor(int node, int k) {
       while(k != 0 && node != -1){
        int path = (int) (int)(Math.log(k &(-k) )/Math.log(2));
        if(path  < par.get(node).size()){
        node = par.get(node).get(path);

        }else{
            return -1;
        }
        k >>= path + 1 ;

       }
       return node;
    }

    public static void main(String[] args) {
        TreeAncestor ta = new TreeAncestor(7,new int[]{-1,0,0,1,1,2,2});
        System.out.println(ta.getKthAncestor(6,3));
//        System.out.println(ta.getKthAncestor(7,3));
        int result = (int)(Math.log(1)/Math.log(2));
        System.out.println(result);
        //System.out.println(ta.getKthAncestor(6,3));
    }
}